#include"QuickSort.h"
#include<stdio.h>
#include<string.h>
void Swap(int* a,int* b){
  int* temp=a;
  a=b;
  b=temp;
}
//快排汉诺塔                                     
int PartSort1(int *a,int left,int right){
  if(left>=right){
    return;
  }
  int key=left;
  int begin=left;
  int end =right;
  while(begin<end){
    while(a[end]>=a[key] && begin<end){
      end--;
    }
    while(a[begin]<=a[key] && begin<end){
      begin++;
    }
    Swap(&a[end],&a[begin]);
  }
  Swap(&a[key],&a[end]);
  key=end;
  PartSort1(a,left,key-1);
  PartSort1(a,key,right);
}
//快排挖坑法                                     
int PartSort2(int *a,int left,int right){
  if(left>=right){
    return;
  }
  int key=a[left];
  int begin=left;                                                                                                                                                                     
  int end =right;
  while(begin<end){
     while(a[end]>=a[key] && begin<end){
       end--;
     }
     a[begin]=a[end];
     while(a[begin]<=a[key] && begin<end){
       begin++;
     }
     a[end]=a[begin];
  }
  a[end]=key;
  PartSort1(a,left,end-1);
  PartSort1(a,end,right);

}        
//快排前后指针                        
int PartSort3(int *a,int left,int right){
  if(left>=right){
    return;
  }
  int key=left;
  int prev=left;                                                                                                                                                                     
  int cur =left+1;
  while(cur<right){
    if(a[cur]<a[key]){
      prev++;
      Swap(&a[prev],&a[cur]);
    }
    cur++;
  }
  Swap(&a[++prev],&a[key]);
  PartSort1(a,left,prev-1);
  PartSort1(a,prev,right);

}      
//快排前后指针
void QuickSort(int *a,int left,int right){
  PartSort3(a,left,right);
}
int main(){
  int array[]={9,8,7,6,5,4,3,2,1,0};
  int n=sizeof(array)/sizeof(int);
  QuickSort(array,0,n-1);
  int a=0;
  for(a=0;a<n;a++){
    printf("%d ",array[a]);
  }
  printf("\n");
  return 0;
}
